from com.example.tree.tree_node import TreeNode
from typing import Optional, List


def beforeOrderTraversal(root: Optional[TreeNode], res: List[int]) -> None:
    """
    前序遍历(递归实现)
    :param res:
    :param root:
    :return:
    """
    if not root:
        return
    res.append(root.val)
    beforeOrderTraversal(root.left, res)
    beforeOrderTraversal(root.right, res)


def inOrderTraversal(root: Optional[TreeNode], res: List[int]) -> None:
    """
    中序遍历(递归实现)
    :param res:
    :param root:
    :return:
    """
    if not root:
        return
    inOrderTraversal(root.left, res)
    res.append(root.val)
    inOrderTraversal(root.right, res)


def postorderTraversal(root: Optional[TreeNode], res: List[int]) -> None:
    """
    后续遍历(递归实现)
    :param res:
    :param root:
    :return:
    """
    if not root:
        return
    postorderTraversal(root.left, res)
    postorderTraversal(root.right, res)
    res.append(root.val)


def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
    if not root:
        return []
    left_res = self.inorderTraversal(root.left)
    right_res = self.inorderTraversal(root.right)
    return left_res + [root.val] + right_res


if __name__ == "__main__":
    #     3
    #    / \
    #   9  20
    #     /  \
    #    15   7
    root = TreeNode(3)
    root.left, root.right = TreeNode(9), TreeNode(20)
    root.right.left, root.right.right = TreeNode(15), TreeNode(7)
    print("==============前序遍历(递归实现)===============")
    lst1 = []
    beforeOrderTraversal(root, lst1)
    print(lst1)
    print("==============中序遍历(递归实现)===============")
    lst2 = []
    inOrderTraversal(root, lst2)
    print(lst2)
    print("==============后序遍历(递归实现)===============")
    lst3 = []
    postorderTraversal(root, lst3)
    print(lst3)
